package com.linyaonan.leetcode.medium._33;

/**
 * @author: Lin
 * @date: 2020/4/27
 */
public class Search {

    public int search(int[] nums, int target) {
        int len = nums.length;
        int left = 0, right = len - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < nums[right]) {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }

    public int search2(int[] nums, int target) {
        // 1. 找到最小值，然后分为两个数组，最左边到最小值前一个位置，最小值到末尾
        int minIndex = getMinIndex(nums, target);
        if (getMatch(nums, 0 , minIndex - 1, target)!= -1) {
            return getMatch(nums, 0, minIndex - 1, target);
        } else {
            return getMatch(nums, minIndex, nums.length - 1, target);
        }
    }

    private int getMinIndex(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            int m = (l + r) >>> 1;
            if (nums[m] > nums[nums.length - 1]) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }

    private int getMatch(int[] nums, int start, int end, int target) {
        while (start < end) {
            int mid = (start + end) >>> 1;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1;
    }

}
